package Math;//给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
//
// 
//
// 进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？ 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,1,3,2,5]
//输出：[3,5]
//解释：[5, 3] 也是有效的答案。
// 
//
// 示例 2： 
//
// 
//输入：nums = [-1,0]
//输出：[-1,0]
// 
//
// 示例 3： 
//
// 
//输入：nums = [0,1]
//输出：[1,0]
// 
//
// 提示： 
//
// 
// 2 <= nums.length <= 3 * 10⁴ 
// -2³¹ <= nums[i] <= 2³¹ - 1 
// 除两个只出现一次的整数外，nums 中的其他数字都出现两次 
// 
// Related Topics 位运算 数组 👍 601 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class singleNumberIII {
    public int[] singleNumber(int[] nums) {
        /**
         * 分组，将只出现一次的数字A/B 和其他出现两次的数字进行分组，
         * A 在一组，B在一组，然后每组中的数进行异或最后得到的就是只出现一次的数
         * 所以分组要按照两个数不同的那一位来分组，比如 1的二进制表示为 001，2的二进制表示为010
         * 因此可以选则第一位或者第二位进行分组 当1和2异或后，为 011，那么为1的位都可以作为分组的位
         * 异或就是相等为0，不相等为1
         * */
        int temp = 0;  //结果为A,B异或的值
        for(int i:nums){
            temp ^= i;
        }
        /**
         * 负数的二进制表示为  正数的二进制表示 反码+1
         * 因此再进行与操作就会保留最右边的1
         * 就可以利用该位作为分组位
         * */
        int group = temp & (-temp);  //保留最右边的1
        int[] arr = new int[2];  //结果
        for(int i : nums){
            //分组位为0的在一组，并且组内异或
            if((group & i) == 0){
                arr[0] ^= i;
            }else{
                //分组位为1的在一组，并且组内异或
                arr[1] ^= i;
            }
        }
        return arr;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
